package 剑指Offer_day04;

import 剑指offer_day02.Offer35;

/**
 * 剑指 Offer 53 - I. 在排序数组中查找数字 I
 *
 * 统计一个数字在排序数组中出现的次数。
 *
 *
 *
 * 示例 1:
 *
 * 输入: nums = [5,7,7,8,8,10], target = 8
 * 输出: 2
 * 示例2:
 *
 * 输入: nums = [5,7,7,8,8,10], target = 6
 * 输出: 0
 *

 *
 * 提示：
 *
 * 0 <= nums.length <= 105
 * -109<= nums[i]<= 109
 * nums是一个非递减数组
 * -109<= target<= 109
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * 使用二分法 解决
 *
 */
public class Offer_53 {

    public int search(int[] nums, int target) {


        int left = 0;

        int right = nums.length-1;

        int mid = (left+right)/2;

        int count = 0;

        while (left<=right){  //只有一个元素的情况

            if (nums[mid]==target) { //找到目标数据
                //向两边查询
                int index = mid;
                while (mid >= 0 && nums[mid] == target) { //先向左查询
                    count++;
                    mid--;
                }

                while (index<nums.length&&nums[index]==target){ //再向右查询
                    count++;
                    index++;
                }

                return count-1; //多计算了一个这里减掉
            }




            if (nums[mid]<target){ //在右边

                left = mid+1;

                mid = (left+right)/2;

            }

            if (nums[mid]> target){ //在左边

                right = mid-1;

                mid = (left+right)/2;

            }


        }



        return count;
    }

    public static void main(String[] args) {


        Offer_53 offer_53 = new Offer_53();

        int search = offer_53.search(new int[]{5, 7, 7, 8, 8, 10}, 8);



    }




}
